package com.lhcai.nk.medium;

/**
 * @author lhcstart
 * @create 2023-02-21 22:10
 */

import java.util.ArrayList;
import java.util.Scanner;

/**
 * 迷宫问题dfs
 */
public class HJ43dfs {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            int m = sc.nextInt();
            int[][] arr = new int[n][m];

            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    arr[i][j] = sc.nextInt();
                }
            }
            // 路径存储的数组
            ArrayList<Pos> list = new ArrayList();
            dfs(arr, 0, 0, list);
            for (Pos p : list) {
                System.out.println("(" + p.x + "," + p.y + ")");
            }
        }
    }

    public static boolean dfs(int[][] arr, int x, int y, ArrayList<Pos> list) {

        //假设此节点可以走
        list.add(new Pos(x, y));
        arr[x][y] = 1;

        if (x == arr.length - 1 && y == arr[0].length - 1) {
            return true;
        }

        //向上
        if (x + 1 < arr.length && arr[x + 1][y] == 0) {
            if (dfs(arr, x + 1, y, list)) {
                return true;
            }
        }

        //向右
        if (y + 1 < arr[0].length && arr[x][y + 1] == 0) {
            if (dfs(arr, x, y + 1, list)) {
                return true;
            }
        }

        //向下
        if (x - 1 > -1 && arr[x - 1][y] == 0) {
            if (dfs(arr, x - 1, y, list)) {
                return true;
            }
        }

        //向左
        if (y - 1 > -1 && arr[x][y - 1] == 0) {
            if (dfs(arr, x, y - 1, list)) {
                return true;
            }
        }
        //回溯
        //走不动,从list里移除
        list.remove(list.size() - 1);
        //重新置为0
        arr[x][y] = 0;
        return false;
    }

    //简单的位置类
    public static class Pos {
        int x;
        int y;

        public Pos(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

}




